package OrderMap;

/**
 * @author Liaorun
 */
public class AvlTree extends AbstractSelfBalancingBinarySearchTree {


    public Node insert(int element) {
        Node newNode = super.insert(element);

        rebalance((AvlNode) newNode);

        return newNode;
    }

    public Node delete(int element) {
        Node deleteNode = super.search(element);

        if (deleteNode != null) {
            Node successorNode = super.delete(deleteNode);
            if (successorNode != null) {
                // if replaced from getMinimun(deleteNode.right) then
                // come back there and
                AvlNode minimum = successorNode.right != null ? getMinimun(successorNode) : (AvlNode) successorNode;

                recomputeHeight(minimum);
                rebalance(minimum);
            } else {
                // 并没有任何节点替代被删除节点的位置
                recomputeHeight((AvlNode) deleteNode.parent);
                rebalance((AvlNode) deleteNode.parent);
            }

            return successorNode;
        }
        return null;
    }

    private AvlNode getMinimun(Node successorNode) {
        return null;
    }

    private void recomputeHeight(AvlNode minimum) {

    }

    private void rebalance(AvlNode node) {
        while (node != null) {
            Node parent = node.parent;

            int leftHeight = node.left == null ? -1 : ((AvlNode) node.left).height;
            int rightHeight = node.right == null ? -1 : ((AvlNode) node.right).height;

            int nodeBalance = rightHeight - leftHeight;

            // rebalance (-2 means left subtree outgrow.
            // 2 mean right subtree
            if (nodeBalance == 2) {
                // 右子树太高左旋
                if (node.right.right != null) {
                    // rr型的不平衡
                    node = avlRotateLeft(node);
                    break;
                } else {
                    // rl型的不平衡
                    node = (AvlNode) doubleRotateRightLeft(node);
                    break;
                }
            } else if (nodeBalance == -2) {
                // 左子树太高右旋
                if (node.left.left != null) {
                    node = (AvlNode) avlRotateRight(node);
                    break;
                } else {
                    node = (AvlNode) doubleRotateLeftRight(node);
                    break;
                }
            } else {
                updateHeight(node);
            }

            node = (AvlNode) parent;
        }
    }

    private void updateHeight(AvlNode node) {

    }

    private Node doubleRotateLeftRight(AvlNode node) {
        return null;
    }

    private Node avlRotateRight(AvlNode node) {
        return null;
    }

    private Node doubleRotateRightLeft(AvlNode node) {
        return null;
    }

    private AvlNode avlRotateLeft(AvlNode node) {
        return null;
    }

    private class AvlNode extends Node {
        public int height;

        public AvlNode(int value) {
            super(value);
        }
    }
}
